"""Just hacked out, experimental ideas here right now"""

print 'pathfind',

"""
m = a.argmin()
m = (m/R, m%R)
M = a.argmax()
M = (M/R, M%R)
ms = [(m,M)]
import random
for i in range(10):
  m = random.randrange(R), random.randrange(R)
  M = random.randrange(R), random.randrange(R)
  if a[m] > a[M]: m,M = M,m
  ms.append((m,M))
"""

# Find sets of local minima and maxima (for evolutionary reasons)

points = [(a[x,y],(x,y)) for y in range(R) for x in range(R)]
points.sort()

print len(points)
ms = []
Ms = []
r = R / 2.0
def d(p1,p2):
  return sum([abs(p1[i]-p2[i]) for i in range(2)])

while len(points) > 1:
  while points and [p for p in ms if d(p,points[0][1]) < r]:
    points.pop(0)
  while points and [p for p in Ms if d(p,points[-1][1]) < r]:
    points.pop()
  if len(points) > 1:
    ms.append(points.pop(0)[1])
    Ms.append(points.pop()[1])

print ms, Ms

# Find paths from all maxima to all minima (instead of from town to
# town, e.g. which is what would make sense)

import pathfinding

# A good heuristic for locating man-made paths
def findflattestpath(start, goal, z):
  def vn_nbhd(p0):
    # Von Neumann neighborhood, wrapping around edges
    return [((p0[0]+dx) % z.shape[0], (p0[1]+dy) % z.shape[1])
            for dx,dy in (-1,0),(1,0),(0,-1),(0,1)]
  def moore_nbhd(p0):
    # Moore neighborhood, wrapping around edges
    # TODO: with his nbhd, should penalize cost by sqrt(2) along
    # diagonals (but I don't, now)
    return [((p0[0]+dx) % z.shape[0], (p0[1]+dy) % z.shape[1])
            for dx,dy in ((-1,-1),(-1, 0),(-1,1),
                          ( 0,-1),        ( 0,1),
                          ( 1,-1),( 1, 0),( 1,1))]
  def dz(p0,p1):
    return abs(z[p1] - z[p0])
  return pathfinding.astar(start, goal, vn_nbhd, dz, dz)

# Finding paths first, then affecting the terrain, which isn't good in
# roadmaking, where following an existing road should be cheaper.

paths = []
for m in ms:
 for M in Ms:
  paths.append(findflattestpath(M, m, a))

for path in paths:
  print '.',
  h = a[M]
  if len(path) < 2: continue
  dh = (a[M] - a[m]) / (len(path) - 1)
  for p in path:
    h = min(h, a[p])
    a[p] = 1.0#h
#for i in range(10):
